package com.scqzy.shengchunqiang.sword2offer.day17;

import java.util.PriorityQueue;

/**
 * @Description: 剑指 Offer 41. 数据流中的中位数
 * @Author 盛春强
 * @Date 2021/8/24 15:17
 */
public class MedianFinder {

    /*
    大小顶堆，各维护不超过一插值的元素
    大顶堆维护较小数（堆顶为较大值）
    小顶堆维护较大数（堆顶为较小值）
    约定若两堆数量相等存入小顶堆,则small.size() >= big.size()
     */
    private PriorityQueue<Integer> small;
    private PriorityQueue<Integer> big;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        small = new PriorityQueue<>();
        big = new PriorityQueue<>((a, b) -> (b - a));
    }

    public void addNum(int num) {
        /*
        精妙写法，写的时候一想就明白了
         */
        if (small.size() == big.size()) {
            big.add(num);
            small.add(big.poll());
        } else {
            small.add(num);
            big.add(small.poll());
        }
    }

    public double findMedian() {
        return small.size() == big.size() ? (small.peek() + big.peek()) / 2.0 : small.peek();
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */